#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "BTree.cpp"

void PreOrder_Path(BTNode *root, char path[], int path_len)
{
    int i;
    if (root == NULL)
        return;

    if (root->lchild == NULL && root->rchild == NULL) // root为叶子结点
    {
        printf("%c到根结点逆路径: %c->", root->value, root->value);
        for (i = path_len - 1; i > 0; i--) // 逆序输出
            printf("%c->", path[i]);
        printf("%c\n", path[0]); // 输出根结点A
    }
    else
    {
        path[path_len] = root->value;                // 将当前结点放入路径中
        path_len++;                                  // 路径长度增1
        PreOrder_Path(root->lchild, path, path_len); // 递归扫描左子树
        PreOrder_Path(root->rchild, path, path_len); // 递归扫描右子树
    }
}

void Longest_Path(BTNode *root, char path[], int path_len, char longest_path[], int &long_path_len)
{
    int i;

    if (root == NULL)
    {
        if (path_len > long_path_len) // 若当前路径更长,将路径保存在longest_path中
        {
            for (i = path_len - 1; i >= 0; i--) // 逆序保存到longest_path
                longest_path[i] = path[i];
            long_path_len = path_len; // 记录最长路径长度
        }
    }
    else
    {
        path[path_len] = root->value;                                            // 将当前结点放入路径中
        path_len++;                                                              // 路径长度增1
        Longest_Path(root->lchild, path, path_len, longest_path, long_path_len); // 递归扫描左子树
        Longest_Path(root->rchild, path, path_len, longest_path, long_path_len); // 递归扫描右子树
    }
}

void PostOrder(BTNode *root)
{
    BTNode *p, *r;
    bool flag;
    BTNode *stack[50];
    int top = -1;
    p = root; // p->A
    do
    {
        while (p != NULL) // 扫描结点p的所有左下结点并进栈
        {
            stack[++top] = p; // 结点p进栈
            p = p->lchild;    // 移动到左孩子
        }
        r = NULL;                 // r指向刚刚访问的结点,初始时为空
        flag = true;              // flag为真表示正在处理栈顶结点
        while (top != -1 && flag) // 栈不空且flag为真时循环
        {
            p = stack[top];     // 取出当前的栈顶结点p
            if (p->rchild == r) // 若结点p的右孩子为空或者为刚刚访问过的结点
            {
                if (p->lchild == NULL && p->rchild == NULL) // 若为叶子结点
                {
                    // 输出栈中所有结点值
                    printf("   %c到根结点逆路径: ", p->value);
                    for (int i = top; i > 0; i--)
                        printf("%c->", stack[i]->value);
                    // 输出根结点
                    printf("%c\n", stack[0]->value);
                }
                top--; // 退栈
                r = p; // r指向刚访问过的结点
            }
            else
            {
                p = p->rchild; // 转向处理其右子树
                flag = false;  // 表示当前不是处理栈顶结点
            }
        }
    } while (top != -1); // 栈不空时循环
}

typedef struct
{
    BTNode *node; // 存放当前结点指针
    int parent;   // 存放双亲结点在队列中的位置
} QuNode;         // 声明顺序队列结点类型

void LevelOrder(BTNode *root)
{
    int k;
    BTNode *p;
    QuNode queue[50];
    int front = -1, tail = -1;
    QuNode e;
    e.node = root;
    e.parent = -1;
    queue[++tail] = e;
    while (front != tail)
    {
        e = queue[++front];
        p = e.node;
        if (p->lchild == NULL && p->rchild == NULL)
        {
            k = front;
            while (queue[k].parent != -1)
            {
                printf("%c->", queue[k].node->value);
                k = queue[k].parent;
            }
            printf("%c\n", queue[k].node->value);
        }
        if (p->lchild != NULL)
        {
            e.node = p->lchild;
            e.parent = front;
            queue[++tail] = e;
        }
        if (p->rchild != NULL)
        {
            e.node = p->rchild;
            e.parent = front;
            queue[++tail] = e;
        }
    }
}

int main(void)
{
    BTNode *b = NULL;
    char tree[50] = "(A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    char *str = tree;

    printf("该二叉树的括号表示方法为：\n");
    CreateBTree(b, str);
    DispBTree(b);
    printf("\n");

    printf("先序遍历的逆路径为：\n");
    char path[50];
    PreOrder_Path(b, path, 0);

    char longest_path[50];
    int longest_path_len = 0;
    printf("最长的逆路径为：\n");
    Longest_Path(b, path, 0, longest_path, longest_path_len);
    for (int i = longest_path_len - 1; i > 0; i--)
        printf("%c->", longest_path[i]);
    printf("%c\n", longest_path[0]);

    printf("后序非递归遍历方法:\n");
    PostOrder(b);

    printf("层次遍历方法:\n");
    LevelOrder(b);

    DestoryBTree(b);
}
